/*
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <hash_map>
#include <set>
#include <vector>
#include <Stack>
#include <iostream>
#include <sstream>
using namespace std;

vector<vector<int>>loadData(int m,int n){
	vector<vector<int>>re;
	int tmp;
	FILE *fp=freopen("data.txt","r",stdin);
	for(int i=0;i<m;i++){
		vector<int>row;
		for(int k=0;k<n;k++){
			fscanf(fp,"%d",&tmp);
			row.push_back(tmp);
		}
		re.push_back(row);
	}
	return re;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
	if(matrix.size()<1)
		return false;
	bool find=false;
	int left=0,right=matrix.size()-1,mid,index=0;
	while(left<=right){
		mid=(left+right)/2;
		if(matrix[mid][0]==target){
			return true;
		}else if(matrix[mid][0]>target){
			right=mid-1;
		}else{
			left=mid+1;
		}
	}
	if(right>=0&&target>matrix[right][0])
		index=right;
	else if(right>0)
		index=right-1;
	left=0;right=matrix[0].size()-1;
	while(left<=right){
		mid=(left+right)/2;
		if(matrix[index][mid]==target){
			return true;
		}else if(matrix[index][mid]>target){
			right=mid-1;
		}else{
			left=mid+1;
		}
	}
	//cout<<index<<endl;
	return false;
}
int main(){
	vector<vector<int>>data=loadData(4,1);
	cout<<searchMatrix(data,7);
	cout<<endl;
	system("pause");
	system("pause");
}
*/